#pragma once
#include <iostream>
#include <set>
#include <map>
#include <assert.h>
using namespace std;
namespace cc
{
    enum colour
    {
        RED,
        BLACK
    };
    template<class K, class V>
    struct RBTnode
    {
        colour _col = RED;
        pair<K, V> _val;
        RBTnode<K, V>* _left = nullptr;
        RBTnode<K, V>* _right = nullptr;
        RBTnode<K, V>* _parent = nullptr;
        RBTnode(const pair<K, V>& x)
            :_val(x)
        {}
    };
    template<class K, class V>
    class RBT
    {
    public:
        typedef RBTnode<K, V> node;
        void reor(node* parent)
        {
            node* sub = parent->_left;
            node* subr = sub->_right;
            if (_root == parent)
            {
                _root = sub;
                sub->_parent = nullptr;
                sub->_right = parent;
                parent->_parent = sub;
                parent->_left = subr;
                if (subr)
                    subr->_parent = parent;
            }
            else
            {
                node* pparent = parent->_parent;
                if (pparent->_left == parent)
                    pparent->_left = sub;
                else
                    pparent->_right = sub;
                sub->_parent = pparent;
                sub->_right = parent;
                parent->_parent = sub;
                parent->_left = subr;
                if (subr)
                    subr->_parent = parent;
            }
        }
        void reol(node* parent)
        {
            node* sub = parent->_right;
            node* subl = sub->_left;
            if (_root == parent)
            {
                _root = sub;
                sub->_parent = nullptr;
                sub->_left = parent;
                parent->_right = subl;
                parent->_parent = sub;
                if (subl)
                    subl->_parent = parent;
            }
            else
            {
                node* pparent = parent->_parent;
                if (pparent->_left == parent)
                    pparent->_left = sub;
                else
                    pparent->_right = sub;
                sub->_parent = pparent;
                sub->_left = parent;
                parent->_right = subl;
                parent->_parent = sub;
                if (subl)
                    subl->_parent = parent;
            }
        }
        bool insert(const pair<K, V>& x)
        {
            if (_root == nullptr)
            {
                _root = new node(x);
                _root->_col = BLACK;
                return true;
            }
            node* parent = nullptr;
            node* cur = _root;
            while (cur)
            {
                if (x.first < cur->_val.first)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (x.first > cur->_val.first)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                    return false;
            }
            cur = new node(x);
            if (x.first < parent->_val.first)
                parent->_left = cur;
            else
                parent->_right = cur;
            cur->_parent = parent;
            //插入完成，准备旋转或是染色
            node* grandfather = parent->_parent;
            while (parent && parent->_col == RED)
            {
                if (grandfather->_left == parent)
                {
                    node* uncle = grandfather->_right;
                    if (uncle && uncle->_col == RED)
                    {
                        uncle->_col = parent->_col = BLACK;
                        if (_root != grandfather)
                            grandfather->_col = RED;
                        else
                            break;
                    }
                    else if (uncle && uncle->_col == BLACK)
                    {
                        if (parent->_left == cur)
                        {
                            reor(grandfather);
                            grandfather->_col = RED;
                            parent->_col = BLACK;
                        }
                        else
                        {
                            reol(parent);
                            reor(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                    else
                    {
                        if (parent->_left == cur)
                        {
                            reor(grandfather);
                            grandfather->_col = RED;
                            parent->_col = BLACK;
                        }
                        else
                        {
                            reol(parent);
                            reor(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
                else
                {
                    node* uncle = grandfather->_left;
                    if (uncle && uncle->_col == RED)
                    {
                        uncle->_col = parent->_col = BLACK;
                        if (_root != grandfather)
                            grandfather->_col = RED;
                        else
                            break;
                    }
                    else if (uncle && uncle->_col == BLACK)
                    {
                        if (parent->_left == cur)
                        {
                            reor(parent);
                            reol(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            reol(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                    else
                    {
                        if (parent->_left == cur)
                        {
                            reor(parent);
                            reol(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            reol(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
                cur = grandfather;
                parent = cur->_parent;
                grandfather = parent->_parent;
            }
            return true;
        }
        void check()
        {
            int x = 0;
            _check(_root, x);
        }
    private:
        node* _root = nullptr;
        void _check(node* root, int x)
        {
            if (root == nullptr)
            {
                cout << x << endl;
                return;
            }
            if (root->_col == RED && (root->_parent && root->_parent->_col == RED))
            {
                cout << "有相同的红色节点出现" << endl;
                assert(false);
            }
            if (root->_col == BLACK)
                x++;
            _check(root->_left, x);
            _check(root->_right, x);
        }
    };
}
